package vip.zhenzicheng.algorithm.leetcode.str;

/**
 * <a href="https://leetcode.cn/problems/minimum-window-substring/">最小覆盖子串 [困难]</a>
 *
 * @author zhenzicheng
 * @date 2022-08-01 16:38
 */
public class MinimumWindowSubstring_76 {

  public String minWindow(String s, String t) {
    // 字典表，记录每个字符出现多少次，s、t都是由字母组成，不会超过给定大小
    int[] tChars = new int[128]; // z -> 122
    int tLen = t.length();
    // 记录t中所有字符的出现次数
    for (int i = 0; i < tLen; i++) {
      // 默认初始化0，指定字符在其出现位置+1
      tChars[t.charAt(i)]++;
    }
    // 滑动窗口左右边界
    int left = 0, right = 0;
    int size = Integer.MAX_VALUE, count = tLen;
    int minSubIndex = 0; // 最小覆盖子串开始位置

    // 遍历所有字符
    while (right < s.length()) {
      char c = s.charAt(right);
      if (tChars[c] > 0) { // 在t中出现过
        count--;
      }
      // 当前字符在tCharts中出现位置的次数-1
      // 当s中存在t中不存在或当前窗口范围内，s中出现的次数大于t中出现的次数时可能为负数
      tChars[c]--;
      // 如果窗口中已经包含了所有字符
      if (count == 0) {
        // 左边界向右递增，出现指定字符在字典表中负数情况说明要么在s中存在t中不存在，要么在s中出现的次数大于t中存在的次数
        // 也即缩短窗口，左边界跳过无效字符
        while (left < right && tChars[s.charAt(left)] < 0) {
          tChars[s.charAt(left)]++; // 复原字典表中已经被减了一次前的结果
          left++;
        }
        // 更新size的最小值
        if (right - left + 1 < size) {
          size = right -left + 1;
          minSubIndex = left;
        }

        // 刚好满足条件时没有执行while还原逻辑
        tChars[s.charAt(left)]++;
        left++;

        count++; // 往下走了一步，没判断的字符就+1
      }
      right++;
    }
    return size == Integer.MAX_VALUE ? "" : s.substring(minSubIndex, minSubIndex + size);
  }

  public static void main(String[] args) {
    System.out.println(Integer.valueOf('a'));
    System.out.println(Integer.valueOf('A'));
    System.out.println(Integer.valueOf('z'));
    System.out.println(Integer.valueOf('Z'));
  }
}
